#include <util.h>
#include <qsort.h>
#include <rand_select.h>

int
rand_partition(int a[], int p, int r)
{
    int i, j;

    srand(time(NULL));
    swap(&a[p+(rand()%(r-p+1))], &a[r]);

    for (i = p-1, j = p; j < r; j++)
    {
        if (a[j] <= a[r])
            swap(&a[++i], &a[j]);
    }
    swap(&a[++i], &a[r]);
    
    return i;
}

int
rand_select(int a[], int p, int r, int i)
{
    int q, k;

    if (p == r)
        return a[p];

    q = rand_partition(a, p, r);
    k = q - p + 1;
    if (k == i)
        return a[q];
    if (k > i)
        return rand_select(a, p, q-1, i);
    else
        return rand_select(a, q+1, r, i-k);
}

int
rand_select_nr(int a[], int p, int r, int i)
{
    int q, k;

    while (p < r)
    {
        q = rand_partition(a, p, r);
        k = q - p + 1;
        if (k == i)
            return a[q];
        if (k > i)
            r = q-1;
        else
            p = q+1, i -= k;
    }

    return a[p];
}

inline int
rand_select_median(int a[], int p, int r)
{
    return rand_select_nr(a, p, r, (r-p+2)/2);
}

int
rand_select_by_median(int a[], int p, int r, int i)
{
    int m, q, k;

    // NOTE: p > r finally if i > n and without this check
    if (p == r)
        return a[p];

    //print_a_range(a, p, r, NULL);
    m = rand_select_median(a, p, r);
    q = partition_ex(a, p, r, m);
    k = q - p + 1;
    //fprintf(stdout, "p %d, r %d, i %d, m %d, q %d, k %d\n", p, r, i, m, q, k);
    if (i == k)
        return a[q];
    if (i < k)
        return rand_select_by_median(a, p, q-1, i);
    return rand_select_by_median(a, q+1, r, i-k);
}

// assume: p < q, r < s, 1<=i<=(n1+n2)
int
ordered_median(int a[], int p, int q, int b[], int r, int s, int i)
{
    // TODO
    // uncomplete idea about this approach: compare two medians
    int k1, k2, m1, m2, n1, n2;
    if (p > q)
        return a[q];
    if (r > s)
        return b[s];

    // index of median
    k1 = (p+q)/2; k2 = (r+s)/2;
    // order statistic of median
    n1 = k1-p+1; n2 = k2-r+1;
    // median
    m1 = a[k1]; m2 = b[k2];
}

#define NOT_FOUND   0x80000000

// assume median is in x[]
static int
find_median(int x[], int low, int high, int y[], int n)
{
    int k;

    if (low > high)
        return NOT_FOUND;

    k = (low + high) / 2;
    if (k == n-1)
    {
        if (x[k] <= y[0])
            return x[k];
        else
            return find_median(x, low, k-1, y, n);
    }
    else if (k < n-1)
    {
        if (y[n-k-2] <= x[k] && x[k] <= y[n-k-1])
            return x[k];
        else if (y[n-k-1] < x[k])
            return  find_median(x, low, k-1, y, n);
        return find_median(x, k+1, high, y, n);
    }
    else
    {
        assert(0);
        return -1;
    }
    /*
    if ( (k == n-1 && x[k] <= y[0]) || (k < n-1 && (y[n-k-1] <= x[k] && x[k] <= y[n-k])) )
        return x[k];
    if (y[n-k] < x[k]) 
        return find_median(x, low, k-1, y, n);
    return find_median(x, k+1, high, y, n);
    */
}

int
two_ordered_array_median(int x[], int y[], int n)
{
    int m;

    if ((m = find_median(x, 0, n-1, y, n)) == NOT_FOUND)
        return find_median(y, 0, n-1, x, n); 

    return m;
}

#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
int 
select_min_max(const int a[], const int p, const int r, int *pMin, int *pMax)
{
#if 0
    int min, max, i, l1, l2;

    if (!a || p > r || !pMin || !pMax)
    {
        iErrno = EINVAL;
        return -1;
    }

    min = max = a[p];

    for (i = p; i <= r; i += 2)
    {
        l1 = a[i];
        if (i == r)
        {
            // only one element left
            if (l1 < min)
                min = l1;
            if (l1 > max)
                max = l1;
            continue;
        }
        l2 = a[i+1];
        // l1 is the bigger one
        if (l1 < l2)
            swap(&l1, &l2);
        if (l1 > max)
            max = l1;
        if (l2 < min)
            min = l2;
    }
    *pMin = min;
    *pMax = max;

    return 0;
#else
    int min, max, i, k, larger, smaller;

    if (!a || p > r || !pMin || !pMax)
    {
        iErrno = EINVAL;
        return -1;
    }
    
    k = r - p + 1;
    if (k % 2)
        min = max = a[p], i = p + 1;
    else
        min = MIN(a[p], a[p+1]), max = MAX(a[p], a[p+1]), i = p + 2;

    while (i < r)
    {
        if (a[i] > a[i+1])
            larger = a[i], smaller = a[i+1];
        else
            larger = a[i+1], smaller = a[i];
        if (larger > max)
            max = larger;
        if (smaller < min)
            min = smaller;

        i += 2;
    }
    *pMin = min;
    *pMax = max;

    return 0;
#endif
}
